#include <vector>
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<bool> isused;
    void dfs(vector<int>& nums,int index)
    {
        if(index>=nums.size())
        {
            ret.push_back(path);
            return;
        }
        for(int i = 0;i<nums.size();i++)
        {
            if(!isused[i])
            {
                path.push_back(nums[index]);
                isused[i] = true;
                dfs(nums,index+1);
                isused[i] = false;
                path.pop_back();
            }
        }
    }//第一种去重的方法为使用一个set，另外一种方法对原数组进行排序，排序之后相同的元素就会，在响铃的
    //位置了
    vector<vector<int>> permute(vector<int>& num) {
        isused.resize(num.size(),false);
       dfs(num,0);
       return ret;
    }
};
//排序后判断相邻的值是否一样
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ret;
    vector<bool> isused;
    void dfs(vector<int>& nums,int index)
    {
        if(index>=nums.size())
        {
            ret.push_back(path);
            return;
        }
        for(int i = 0;i<nums.size();i++)
        {
            if(isused[i])
                continue;
            if(i>0&&nums[i-1] == nums[i]&&!isused[i - 1])
                continue;
            //如果前一个元素 ​没有被使用过，则跳过当前元素，避免生成重复的排列。
            //如果前一个元素 ​已经被使用过，则允许使用当前元素，因为前一个元素已经被纳入当前排列中，不会导致重复。这里的这个isused的目的是上面的两个
            path.push_back(nums[i]);
            isused[i] = true;
            dfs(nums,index+1);
            path.pop_back();
            isused[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& num) {
        sort(num.begin(),num.end());
        isused.resize(num.size(),false);
        dfs(num,0);
        return ret;
    }
};